package com.gy.dyanmic;

/**
 * 背包问题
 */
public class KnapsbackProblemTest {


    public static void main(String[] args) {
        int[] w={1,4,3,5,2};//物品的重量
        int[] val={1500,3000,2000,1000,5000};//物品的价值
        int m=6;//背包的容量
        int n=val.length;

        //创建动态规划二维数组
        int[][] arr=new int[n+1][m+1];
        //创建结果数组
        int[][] res=new int[n+1][m+1];
        
        //初始化
        for (int i = 0; i < arr.length; i++) {
            arr[i][0]=0;
        }
        for (int i = 0; i < arr[0].length; i++) {
            arr[0][i]=0;
        }

        //动态规划
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                if (w[i-1]>j){
                    arr[i][j]=arr[i-1][j];
                }else {
                    /*arr[i][j]=Math.max(arr[i-1][j],val[i-1]+arr[i-1][j-w[i-1]]);*/
                    if (arr[i-1][j]<(val[i-1]+arr[i-1][j-w[i-1]])){
                        arr[i][j]=val[i-1]+arr[i-1][j-w[i-1]];
                        res[i][j]=1;
                    }else {
                        arr[i][j]=arr[i-1][j];
                    }
                }
            }
        }


        for (int[] row : arr) {
            for (int data : row) {
                System.out.printf("%5d\t",data);
            }
            System.out.println();
        }


        //逆向遍历res得出方案
        int i= res.length-1;
        int j= res[0].length-1;

        while (i>0&&j>0){
            if (res[i][j]==1){
                System.out.printf("第%d个商品放入到背包\n",i);
                j-=w[i-1];
            }
            i--;
        }
    }
}
